package com.mango.algorithm.tree.binary;

import com.mango.data.structure.binarytree.linknode.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 判断 完全二叉树
 * 完全二叉树是满二叉树的一部分，1到h-1层是满二叉树，h层节点集中在左边。
 * @Author: mango
 * @Date: 2022/4/12 10:19 下午
 */
public class CompleteTree {
    public boolean isCompleteTree(TreeNode root) {
        if(root == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 可能是叶子节点
        boolean shouldBeLeaf = false;
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            // 如果右节点不空，左节点为空，则不是完全二叉树
            if(cur.right != null && cur.left == null){
                return false;
            }
            // 可能是叶子节点，且左节点或者右节点不为空的，则不是完全二叉树
            if(shouldBeLeaf && (cur.left != null || cur.right != null)){
                return false;
            }
            if(cur.left != null){
                queue.offer(cur.left);
            }else{
                shouldBeLeaf = true;
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }else{
                shouldBeLeaf = true;
            }
        }
        return true;
    }
}

